一、棧
1.棧的概念

? ? 棧：一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作。 進行數據插入和刪除操作的一端稱為棧頂，另一端稱為棧底。
? ? 棧中的數據元素遵守后進先出LIFO（Last In First Out）的原則。 壓棧：棧的插入操作叫做進棧/壓棧/入棧，入數據在棧頂。
? ? 出棧：棧的刪除操作叫做出棧。出數據也在棧頂。

2.棧的實現

棧的實現一般可以使用數組或者鏈表實現，相對而言數組的結構實現更優一些。因為數組在尾上插入數據的代價比較小。

3.代碼示例

（1）Stack.h

?

//頭文件的聲明
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

2.棧的接口定義

//棧的接口定義
typedef int STDataType;
typedef struct Stack
{
? ? STDataType* a;
? ? int top;
? ? int capacity;
}ST;

3.初始化和銷毀函數的聲明

//初始化
void STInit(ST* ps);
//銷毀
void STDestroy(ST* ps);

4.入棧和出棧函數的聲明

//插入
void STPush(ST* ps, STDataType x);
//刪除
void STPop(ST* ps);

5.查找棧頂元素和長度計算函數以及判空函數的聲明

//插入
//查找棧頂元素
STDataType STTop(ST* ps);
//長度計算
int STSize(ST* ps);
//判斷是否為空
bool STEmpty(ST* ps);